#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
int n;
namespace Brute{

int main(){
    vector<ll>tmp;ll x;
    while(n--){
        cin>>x;
        auto it=lower_bound(tmp.begin(),tmp.end(),x);
        if(it==tmp.end()||*it!=x)tmp.insert(it,x);
        else tmp.erase(it);
        int len=tmp.size();ll s1=0,s2=0,ans=0;
        pll now={0,0};
        for(int i=0;i<len;++i){
            s1+=tmp[i];s2+=tmp[len-i-1];
            if(s1<s2)
                if(s1<=now.se)now.se=s2;
                else ans+=now.se-now.fi,now={s1,s2};
        }
        ans+=now.se-now.fi;
        printf("%lld\n",ans);
    }
    return 0;
}

}
namespace Test{

#define ls p<<1
#define rs p<<1|1
const int N=4e5+3;
bitset<N>vis;
ll t[N<<2];
int s[N<<2];
int m;
vector<ll>a,b;
void upd(int x,int l=0,int r=m-1,int p=1){
    if(l==r){t[p]=vis[l]*b[l];s[p]=vis[l];return;}
    int mid=l+r>>1;
    if(x<=mid)upd(x,l,mid,ls);
    else upd(x,mid+1,r,rs);
    s[p]=s[ls]+s[rs];
    t[p]=t[ls]+t[rs];
}
ll getPre(int k,int l=0,int r=m-1,int p=1){
    if(!k)return 0;
    ll ans=0;begin:;
    if(l==r)return ans+t[p];
    int mid=l+r>>1;
    if(s[ls]>=k)r=mid,p=ls;
    else ans+=t[ls],k-=s[ls],l=mid+1,p=rs;
    goto begin;
}
ll getSuf(int k,int l=0,int r=m-1,int p=1){
    if(!k)return 0;
    ll ans=0;begin:;
    if(l==r)return ans+t[p];
    int mid=l+r>>1;
    if(s[rs]>=k)l=mid+1,p=rs;
    else ans+=t[rs],k-=s[rs],r=mid,p=ls;
    goto begin;
}
int main(){
    a.resize(n);b.resize(n);
    for(int i=0;i<n;++i)cin>>a[i],b[i]=a[i];
    sort(b.begin(),b.end());b.erase(unique(b.begin(),b.end()),b.end());
    m=b.size();
    for(auto &x:a)x=lower_bound(b.begin(),b.end(),x)-b.begin();
    set<ll>s;
    for(auto x:a){
        if(!vis[x])vis[x]=1,upd(x),s.insert(b[x]);
        else vis[x]=0,upd(x),s.erase(b[x]);
        auto getDiv=[&](){
            int l=0,r=s.size(),mid,ans=0;
            for(;l<=r;getPre(mid)<getSuf(mid)?l=mid+1,ans=mid:r=mid-1)mid=l+r>>1;
            return ans;
        };
        ll mx=getSuf(getDiv());
        auto L=s.begin();auto R=s.rbegin();
        ll s1=0,s2=0,ans=0;pll now={0,0};
        while(L!=s.end()){
            s1+=*L;s2+=*R;
            if(s1>=s2)break;
            if(s1<=now.se){now.se=mx;break;}
            else ans+=now.se-now.fi,now={s1,s2};
            ++L;++R;
        }
        ans+=now.se-now.fi;
        printf("%lld\n",ans);
    }
    return 0;
}

}
int main(){
    freopen("kte.in","r",stdin);
    freopen("kte.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n<=3e4)return Brute::main();
    return Test::main();
    return 0;
}